package com.zjsru.oneDay202212;

/**
 * @Author: CookLee
 * @Date: 2022/12/9
 *
 * 判断一个数字是否可以表示成三的幂的和
 * 对于一个整数 y ，如果存在整数 x 满足 y == 3x ，我们称这个整数 y 是三的幂。
 * 1 <= n <= 10^7
 *
 * 输入：n = 91
 * 输出：true
 * 解释：91 = 3^0 + 3^2 + 3^4
 */
public class CheckPowersOfThree {
    
    /**
     * 循环 每次除以3 直到 除不下为止
     */
    public boolean checkPowersOfThree(int n) {
        while (n > 0) {
            //判断包含3^0的情况，所以==1
            if (((n % 3) == 0) || ((n % 3) == 1)) {
                n = n / 3;
            } else {
                return false;
            }
        }
        return true;
    }
    
    /**
     * 递归
     */
    public boolean checkPowersOfThree2(int n) {
        return recursive(n) == 0;
    }
    
    public Integer recursive(int n) {
        // 0 和 1 表示是3的幂次除后的数字
        if (n == 0 || n == 1) {
            return 0;
        } else if (n == 2) {
            return -1;
        }
        //考虑例如11 这类直接不符合要求的数字
        if (((n % 3) == 0) || ((n % 3) == 1)) {
            n = n / 3;
        } else {
            return -1;
        }
        return recursive(n);
    }
    
    public static void main(String[] args) {
        CheckPowersOfThree checkPowersOfThree = new CheckPowersOfThree();
        int n = 91;
        System.out.println(checkPowersOfThree.checkPowersOfThree2(n));
    }
}
